package q62_uniquePaths;

public class Solution_2 {
    public static void main(String[] args) {
        Solution_2 s = new Solution_2();

    }

    /**
     * 由于我们每一步只能从向下或者向右移动一步，因此要想走到从0到(i,j)这个位置
     * 只有两个点能到 (i,j) ——> (i - 1, j) , (i, j - 1)
     * 容易理解的是： 对于到(i,j)这个点的方法，相当于到(i - 1, j) , (i, j - 1)这两个点的方法只和
     * 所以，我们可以获得m,n范围内任何一点的到达总方法数量，也就是某点方法等于上面方法和左边方法这两个数的和
     * 因此使用一个二维的矩阵很容易实现
     * 首先矩阵的上边和左边所有的值都是1，然后求每个点只需要加上左两个格子的值即可
     *
     * 如果是一个三维场景的该问题
     * 那么初始化时可以将三个面初始化为对应的数值
     * 例如f[i][j][0] f[i][0][j] f[0][i][j]
     * 而递推公式是一样的
     * f[i][j][k] = f[i - 1][j][k] + f[i][j - 1][k] + f[i][j][k - 1];
     */
    public int uniquePaths(int m, int n) {
        int[][] f = new int[m][n];
        // 先将上左两侧的值置1
        for (int i = 0; i < m; ++i) {
            f[i][0] = 1;
        }
        for (int j = 0; j < n; ++j) {
            f[0][j] = 1;
        }
        // 到(i,j)这个点的方法，相当于到(i - 1, j) , (i, j - 1)这两个点的方法和
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; ++j) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }

        // 得到答案
        return f[m - 1][n - 1];
    }
}
